import java.util.List;

class LinkedList{
    //头结点
    private ListNode head;
    //头插法
    public void addFirst(int val){
        ListNode node=new ListNode(val);
        if(head!=null){
            node.next = head;
        }
        //head==null也会走这里
        head = node;
    }
    //遍历
    public void display(){
        ListNode cur=head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }

    public ListNode getHead() {
        return head;
    }

    public void setHead(ListNode head) {
        this.head = head;
    }
}

public class Test {
    // 反转一个单链表。
    public static ListNode reverseList(ListNode head) {
        if(head == null) return null;//说明链表是空的
        if(head.next == null) return head;//说明只有1个节点
        //多个节点
        ListNode cur=head;//领头羊 用来记录下一个节点
        ListNode pre=null;//记录上一个节点
        while (cur!=null){
            cur=head.next;
            head.next=pre;
            pre=head;
            head=cur;
        }
        return pre;
    }
    // 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
    // 如果有两个中间结点，则返回第二个中间结点
    public static ListNode middleNode(ListNode head) {
       ListNode cur=head;
       ListNode tmp=head;
       while (cur!=null&&cur.next!=null){
           cur=cur.next.next;
           tmp=tmp.next;
       }
       return tmp;
    }
    //4. 输入一个链表，输出该链表中倒数第k个结点。
    public static ListNode FindKthToTail(ListNode head,int k){
        if(k<=0||head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while (k-1!=0){
            fast=fast.next;
            if(fast==null){
                return null;//k太大了超出链表范围
            }
            k--;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }

    

    public static void main(String[] args) {
        LinkedList list=new LinkedList();
        list.addFirst(99);
        list.addFirst(78);
        list.addFirst(56);
        list.addFirst(34);
        list.addFirst(12);
        list.display();
        list.setHead(reverseList(list.getHead()));
        list.display();
        list.setHead(middleNode(list.getHead()));
        list.display();
    }

}
